using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class BSPTree 
{

    public BSPNode root;
    public List<BSPNode> leafNodes;
    public List<BSPRectangle> oldSplits;
    public List<BSPRectangle> newSplits;
    //System.Random random;
    PseudoRandom.MersenneTwister random;
    int maxFail;

    public BSPTree(PseudoRandom.MersenneTwister random)
    {
        InitTree(new BSPRectangle(0, 0, BSPConfig.DefaultCellWidth, BSPConfig.DefaultCellHeight), random);
    }

    public BSPTree(BSPRectangle cellSize, PseudoRandom.MersenneTwister random)
    {
        InitTree(cellSize, random);
      
    }

    private void InitTree(BSPRectangle cellSize, PseudoRandom.MersenneTwister random)
    {
        this.random = random;
        root = new BSPNode(cellSize, random);
        leafNodes = new List<BSPNode>();
        leafNodes.Add(root);
        oldSplits = new List<BSPRectangle>();
        newSplits = new List<BSPRectangle>();
    }

    public void ClearRooms()
    {
        root.ClearRooms();
    }

    public void SplitNodes(int splitCount)
    {
        //clear out old rooms
        root.ClearRooms();

        for (int i = 0; i < splitCount; i++)
        {
            //shift the link for leafs over and reset
            //must use new because a clear would nuke the leafs
            List<BSPNode> oldLeafs = leafNodes;
            leafNodes = new List<BSPNode>();
            //Debug.Log("oldLeaf count: " + oldLeafs.Count.ToString());
            //merge the new splits into old.
            oldSplits.AddRange(newSplits);
            //Debug.Log("oldSplit count: " + oldSplits.Count.ToString());
            newSplits.Clear();
            foreach (BSPNode curNode in oldLeafs)
            {
                //determine direction
                //force it?
                bool splitVertical = false;
                if (((float)curNode.cellSize.width / curNode.cellSize.height) < BSPConfig.MinHorizontalRatio)
                {
                    splitVertical = false;
                }
                else if (((float)curNode.cellSize.height / curNode.cellSize.width) < BSPConfig.MinVerticalRatio)
                {
                    splitVertical = true;
                }
                else
                {
                    if (random.genrand_uint32() % 2 == 0) splitVertical = true;
                    else splitVertical = false;
                }
                //find split point and create
                //splitVertical = false;
                if (splitVertical)
                {
                    int minX = (int)(curNode.cellSize.width * BSPConfig.minXSplit);
                    int maxX = (int)(curNode.cellSize.width * BSPConfig.maxXSplit);
                    BSPRectangle splitPoint = new BSPRectangle(0, 0, 0, 0);
                    splitPoint.x = random.genrand_N(maxX - minX + 1) + minX;
                    splitPoint.width = 1;
                    splitPoint.height = curNode.cellSize.height;
                    //offset
                    splitPoint.x += curNode.cellSize.x;
                    splitPoint.y += curNode.cellSize.y;
                    //add to node and split list
                    newSplits.Add(splitPoint);
                    curNode.splitPoint = splitPoint;
                }
                else
                {
                    int minY = (int)(curNode.cellSize.height * BSPConfig.minYSplit);
                    int maxY = (int)(curNode.cellSize.height * BSPConfig.maxYSplit);
                    BSPRectangle splitPoint = new BSPRectangle(0, 0, 0, 0);
                    splitPoint.y = random.genrand_N(maxY - minY + 1) + minY;
                    splitPoint.height = 1;
                    splitPoint.width = curNode.cellSize.width;
                    //offset
                    splitPoint.x += curNode.cellSize.x;
                    splitPoint.y += curNode.cellSize.y;
                    //add to node and split list
                    newSplits.Add(splitPoint);
                    curNode.splitPoint = splitPoint;

                    if (splitPoint.y > 512) Debug.LogError("splitPoint.y exceeds 512: " + splitPoint.y.ToString());
                }
                
                //create children
                if (splitVertical)
                {
                    curNode.children[0] = new BSPNode(new BSPRectangle(curNode.cellSize.x, curNode.cellSize.y, curNode.splitPoint.x - curNode.cellSize.x, curNode.cellSize.height), random);
                    curNode.children[1] = new BSPNode(new BSPRectangle(curNode.splitPoint.x, curNode.splitPoint.y, curNode.cellSize.width - curNode.children[0].cellSize.width, curNode.cellSize.height), random);
                }
                else
                {
                    curNode.children[0] = new BSPNode(new BSPRectangle(curNode.cellSize.x, curNode.cellSize.y, curNode.cellSize.width, curNode.splitPoint.y - curNode.cellSize.y), random);
                    curNode.children[1] = new BSPNode(new BSPRectangle(curNode.splitPoint.x, curNode.splitPoint.y, curNode.cellSize.width, curNode.cellSize.height - curNode.children[0].cellSize.height), random);
                }
                curNode.children[0].sister = curNode.children[1];
                curNode.children[1].sister = curNode.children[0];
                curNode.children[0].parent = curNode;
                curNode.children[1].parent = curNode;
                leafNodes.Add(curNode.children[0]);
                leafNodes.Add(curNode.children[1]);
            } //end foreach on nodes
        }//end for on split count
            
    }//end SplitNodes()


    public void GenerateRooms()
    {
        //over each rooms
        //Debug.Log(leafNodes.Count.ToString());
        foreach (BSPNode curLeaf in leafNodes)
        {
            curLeaf.GenerateRoom();
        }
    }

    public void GenerateCorridors()
    {
        maxFail = 0;
        while (root.myRoom == null)
        {
            ConnectSides(root);
        }
        Debug.Log("Max Fail Count: " + maxFail.ToString());
    }

    public void ConnectSides(BSPNode node)
    {
        int failCount = 0;
        BSPRectangle newCorridor;        

        if (node.children[0].myRoom == null)
        {
            ConnectSides(node.children[0]);
            ConnectSides(node.children[1]);
        }
        else
        {
            //working copies of the rooms lists
            List<BSPRectangle> child1Rooms = new List<BSPRectangle>(node.children[0].childRooms);
            List<BSPRectangle> child2Rooms = new List<BSPRectangle>(node.children[1].childRooms);
            //join sides
            bool keepTrying = true;
			 
            while(keepTrying)
            {
                if (failCount > 100000) throw new System.Exception("Fail > 100,000");
                //random room on two sides
                int r1 = random.genrand_N(child1Rooms.Count);
                int r2 = random.genrand_N(child2Rooms.Count);
                //verticle or horizontal?
                if (node.splitPoint.width == 1)
                {
                    //changed to +1 / -2 to avoid corners
                    int yMin = Mathf.Max(child1Rooms[r1].y + 1, child2Rooms[r2].y + 1);
                    int yMax = Mathf.Min(child1Rooms[r1].bottom - 1, child2Rooms[r2].bottom - 1) - 1;
                    //overlap?
                    if (yMin >= yMax)
                    {
                        //no overlap, so continue
                        failCount++;
                        continue;
                    }
                    //yes overlap
                    //find x start point
                    int xStart = child1Rooms[r1].x + child1Rooms[r1].width;
                    //find width
                    int xWidth = child2Rooms[r2].x - xStart;
                    //create rectangle                    
                    newCorridor = new BSPRectangle(xStart, random.genrand_N(yMax - yMin + 1) + yMin, xWidth, 1, BSPRectangle.RectangleType.Corridor);
                }//end vertical split
                else  //horizontal split
                {
                    //changed to +1 / -2 to avoid corners
                    int xMin = Mathf.Max(child1Rooms[r1].x + 1, child2Rooms[r2].x + 1);
                    int xMax = Mathf.Min(child1Rooms[r1].right - 1, child2Rooms[r2].right - 1) - 2;
                    //overlap?
                    if (xMin >= xMax)
                    {
                        //no overlap, so continue
                        failCount++;
                        continue;
                    }
                    //yes overlap
                    //find y start point
                    int yStart = child1Rooms[r1].y + child1Rooms[r1].height;
                    //find width
                    int yHeight = child2Rooms[r2].y - yStart;
                    //create rectangle
                    newCorridor = new BSPRectangle(random.genrand_N(xMax - xMin + 1) + xMin, yStart, 1, yHeight, BSPRectangle.RectangleType.Corridor);                    
                } //end horizontal split

                //test collisions
                bool collisionFail = false;
                for (int index = 0; index < child1Rooms.Count; index++)
                {
                    if (index == r1) continue;
                    if (child1Rooms[index].Intersects(newCorridor))
                    {
                        //fail
                        collisionFail = true;
                        //remove room
                        child1Rooms.RemoveAt(r1);
                        if (child2Rooms.Count == 0) throw new System.Exception("ran out of rooms!");
                        break;
                    }
                }
                if (collisionFail)
                {
                    failCount++;
                    continue;
                }
                for (int index = 0; index < child2Rooms.Count; index++)
                {
                    if (index == r2) continue;
                    if (child2Rooms[index].Intersects(newCorridor))
                    {
                        //fail
                        collisionFail = true;
                        //remove rooms
                        child2Rooms.RemoveAt(r2);
                        if (child2Rooms.Count == 0) throw new System.Exception("ran out of rooms!");
                        break;
                    }
                }
                if (collisionFail)
                {
                    failCount++;
                    continue;
                }
                //allright!  made it this far so valid corridor
                node.myRoom = newCorridor;
                node.AddRoom(newCorridor);
                keepTrying = false;

            }//end keep trying
        }//end else for recursion

        Debug.Log("Fail Count for Corridor: " + failCount.ToString());
        if (failCount > maxFail) maxFail = failCount;
    }//end ConnectSides
}

